package com.zhengb.algorithmdemo.leetcode.linklist.easy;

import com.zhengb.algorithmdemo.leetcode.linklist.ListNode;

/**
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 *
 * @author zhengbo
 * @date 2020/3/21
 */
public class TwoNumbersSum {

    public static void main(String[] args) {
        //(2 -> 4 -> 3) + (5 -> 6 -> 4)

//        ListNode two = new ListNode(2);
//        ListNode four = new ListNode(4);
//        ListNode three = new ListNode(3);
//        ListNode seven = new ListNode(7);
//
//        two.next = four;
//        four.next = three;
//
//        ListNode five = new ListNode(5);
//        ListNode six = new ListNode(6);
//        ListNode four2 = new ListNode(4);
//        five.next = six;
//        six.next = four2;
//
//
//
//        ListNode fisrt = new ListNode(5);
//        ListNode secon = new ListNode(5);

        ListNode two = new ListNode(2);
        ListNode nine1 = new ListNode(9);
        ListNode nine2 = new ListNode(9);

        two.next = nine1;
        nine1.next = nine2;

        ListNode two1 = new ListNode(2);
        ListNode nine3 = new ListNode(9);
        ListNode nine4 = new ListNode(9);

        two1.next = nine3;
        nine3.next = nine4;


//        ListNode zero = new ListNode(0);
//
//        ListNode seven = new ListNode(7);
//        seven.next = new ListNode(3);

        ListNode listNode = addTwoNumbers(two, two1);

        System.out.println(listNode);

    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        //第一个链表当前节点指针
        ListNode firstPointer = l1;
        //第二个链表当前节点指针
        ListNode secondPointer = l2;

        ListNode resultHeadNode = null;

        //当前指针为累加需要累进数
        int curAdd = 0;

        //临时节点 用于指向结果连接的尾结点
        ListNode tempNode = null;

        while (firstPointer != null || secondPointer != null) {

            int curPositionValue;

            int curSum = (firstPointer != null ? firstPointer.val : 0) +
                    (secondPointer != null ? secondPointer.val : 0) + curAdd;

            //小于10 不需要累进
            if (curSum < 10) {
                curPositionValue = curSum;
                curAdd = 0;
            } else {
                //大于10  累进1位
                curPositionValue = curSum % 10;
                curAdd = 1;
            }

            ListNode curNode = new ListNode(curPositionValue);

            //头结点为空
            if (resultHeadNode == null) {
                resultHeadNode = curNode;
            } else {
                //尾节点的next指向累加结果
                tempNode.next = curNode;
            }
            //tempNode设置为尾节点
            tempNode = curNode;

            //移动指针
            if (firstPointer != null) {
                firstPointer = firstPointer.next;
            }
            if (secondPointer != null) {
                secondPointer = secondPointer.next;
            }
        }
        //所有指针移动完成后，累进值不为0 则添加累进值为尾节点
        if (curAdd != 0) {
            tempNode.next = new ListNode(curAdd);
        }

        return resultHeadNode;
    }
}
